#include<bits/stdc++.h>
#define sd(n) scanf("%d",&n) 
#define sld(n) scanf("%lld",&n)
#define pd(n) printf("%d", (n))
#define pld(n) printf("%lld", n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
const int N=2e5;
const int maxn=1e6;
#define INF 0x7fffffff
typedef long long int ll;
using namespace std;
//----------------------------------------------------------------------------//
int a[N+10];
pair<int,int> b[N+10];//每对朋友
int c[N+10];//记录每个人出现的次数
//每个不被邀请的人有一个不开心值,被邀请的人中如果有两个人互为朋友,则蛋糕数+1
//要求蛋糕数为偶数的同时保证最小值
void solve()
{
	memset(c,0,sizeof(c));
	int n,m;
	sd(n);sd(m);

	for(int i=1;i<=n;i++) sd(a[i]);
	for(int i=1;i<=m;i++)
	{
		sd(b[i].fi);
		sd(b[i].se);
		c[b[i].fi]++;
		c[b[i].se]++;
	}
	if(m%2==0)//m为偶数直接输出
	{
		pd(0);
		puts("");
		return;
	}

	int ans=1e9;//m为奇数,删除一个人(这人有奇数个朋友),删除两个人(两人都有偶数个朋友,且两者互为朋友)
	for(int i=1;i<=n;i++)
	{
		if(c[i]%2!=0)
			ans=min(ans,a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		if(c[b[i].fi]%2==0&&c[b[i].se]%2==0)
			ans=min(ans,(a[b[i].fi]+a[b[i].se]));
	}
	pd(ans);
	puts("");


}

int main()
{
	int T;
	sd(T);
	while (T--)
	{
		solve();
	}
	return 0;
}